class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        diff = [0] * n
        for i in range(1, n):
            diff[i] = prices[i] - prices[i - 1]
        DP = [[[0 for _ in range(n)] for _ in range(2)] for _ in range(k + 1)]
        max_val = 0
        for i in range(1, n):
            for t in range(min(i // 2 + 1, k)):
                DP[t + 1][0][i] = max(DP[t + 1][0][i - 1] + diff[i], DP[t][1][i - 1] + diff[i])
                DP[t + 1][1][i] = max(DP[t + 1][1][i - 1], DP[t + 1][0][i - 1])
                max_val = max(DP[t + 1][0][i], DP[t + 1][1][i], max_val)
        return max_val


data = Solution()
k = 2
prices = [2, 4, 1]
print(data.maxProfit(k, prices))
k = 2
prices = [3, 2, 6, 5, 0, 3]
print(data.maxProfit(k, prices))
k = 2
prices = [2, 1, 2, 0, 1]
print(data.maxProfit(k, prices))
